package com.wangjie.stackandqueue;

/**
 * @author jieshao
 * @date 2022/5/12 17:54
 * 
 * 1541. 平衡括号字符串的最少插入次数
 */
public class Test05 {
    public static void main(String[] args) {
        String s = "()((";
        int res = minInsertions(s);
        System.out.println(res);
    }

    public static int minInsertions(String s) {
        // 记录插入次数
        int res = 0;
        // 记录右括号的需求量
        int need = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                need += 2;
                if (need % 2 == 1) {
                    // 插入一个右括号
                    res++;
                    // 对右括号的需求 -1
                    need--;
                }
            }
            if (c == ')') {
                need--;
                // 说明右括号太多了
                if (need == -1) {
                    // 需要插入一个左括号
                    res++;
                    // 同时，对右括号的需求变为 1
                    need = 1;
                }
            }
        }
        return res + need;
    }
}